package demo;


/**
 *  合并两个有序数组
 */
class Solution15 {
	public void merge(int[] nums1, int m, int[] nums2, int n) {
		if (nums1.length == 0 && nums2.length == 0) {
			return;
		}
		for (int i = m; i < m + n; i++) {
			nums1[i] = nums2[i-m];
		}
		System.out.println(nums1);
		// 排序数组
		quickSort(nums1, 0, nums1.length - 1);
	}

	private void quickSort(int[] nums, int l, int r) {
		if (l < r) {
			int privot = partition(nums, l, r);
			quickSort(nums, l, privot - 1);
			quickSort(nums, privot + 1, r);
		}

	}

	private int partition(int[] nums, int l, int r) {
		int privot = nums[r];
		while(l < r) {
			while (l < r && nums[l] < privot) {
				l++;
			}
			nums[r] = nums[l];
			while (l<r && nums[r] >= privot) {
				r--;
			}
			nums[l] = nums[r];
		}
		nums[l] = privot;
		return l;
	}

	public static void main(String[] args) {
		int[] nums = new int []{2,3,1,7,9,5,6};
		new Solution15().quickSort(nums, 0, nums.length -1);
	}
}

